package com.java.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 冒泡排序:双层的for循环，时间复杂度O(n^2)
 * 每一趟排序，就会将最大的数排在最后
 */
public class BubbleSort {

    public static void main(String[] args) {

//        int arr[] = {2,6,7,5,1,9,4,-1};

        //随机产生一个数组
        int[] array = new int[10];
        for (int i = 0; i < 10; i++) {
            array[i] = (int) (Math.random() * 100);
        }

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间："+date1Str);

        bubble(array);

        System.out.println("=======排序后========================");
        System.out.println(Arrays.toString(array));

        Date date2 = new Date();
        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date2Str = simpleDateFormat2.format(date2);
        System.out.println("排序前的时间："+date2Str);
    }




    public static void bubble(int[] arr){

        //优化的一个方式
        boolean flag = false;//标识变量，标识是否进行过交换

        int temp = 0;//临时变量
        //总共要循环arr.length - 1次
        for (int j = 0; j < arr.length - 1; j++) {
            //i < arr.length-1-j:是因为每一趟排序都会找出最大值，所以下一次排序比上一次排序少一次
            for (int i = 0 ; i < arr.length-1-j  ; i++) {
                if (arr[i] > arr[i+1]){
                    flag = true;//进行过排序，置为true
                    //交换数据
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }

//            System.out.println(Arrays.toString(arr));

            if (!flag){ //flag == false 在一趟排序中，一次都没有交换过,表示其实排序好了，
                break; //排序好了，就不需要再进行下面的循环了，直接 break
            }else {
                flag = false; //因为上面排序置为了true，所以这里要再次置为false
            }
        }

    }






}
